package 典型.并查集;

/**
 * @Classname UnionFind
 * @Description TODO
 * @Date 2021/4/20 19:48
 * @Created by yin
 */
public class UnionFind {
    private final int[] parent; // 父节点
    private int count; // 连通分量的数量

    public UnionFind(int n) {
        this.count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int findRoot(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public void union(int p, int q) {
        int rootx = findRoot(p);
        int rooty = findRoot(q);
        if (rootx == rooty) return;
        parent[p] = q;
        count--;
    }

    public int getCount(){
        return count;
    }
}
